#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
using namespace std;

struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
void push_back(ListNode* head, ListNode* newnode)
{
    ListNode* cur = head;
    while (cur->next != nullptr)
    {
        cur = cur->next;
    }
    cur->next = newnode;
}
ListNode* reverse(ListNode* head)
{
    ListNode* LinkNode = nullptr;
    ListNode* cur = head;
    ListNode* nextNode = cur->next;
    while (cur)
    {
        cur->next = LinkNode;
        LinkNode = cur;
        cur = nextNode;
        if (nextNode != nullptr)
            nextNode = nextNode->next;
    }
    return LinkNode;
}
ListNode* addInList(ListNode* head1, ListNode* head2)
{
    if (head1->val == 0 && head2->val == 0) return new ListNode(0);
    ListNode* result = new ListNode(-1);
    ListNode* tail = result;
    head1 = reverse(head1);
    head2 = reverse(head2);
    ListNode* num1 = head1, * num2 = head2;
    int carry = 0;
    while (num1 || num2 || carry)
    {
        int n1 = num1 == nullptr ? 0 : num1->val;
        int n2 = num2 == nullptr ? 0 : num2->val;
        int sum = n1 + n2 + carry;
        ListNode* newnode = new ListNode(sum % 10);
        tail->next = newnode;
        tail = tail->next;
        carry = sum / 10;
        if(num1) num1 = num1->next;
        if(num2) num2 = num2->next;
    }
    return reverse(result->next);
}
int main()
{
    ListNode l1(9);
    ListNode l2(3);
    ListNode l3(7);
    l1.next = &l2;
    l2.next = &l3;

    ListNode ll1(6);
    ListNode ll2(3);
    ll1.next = &ll2;

    ListNode* r = addInList(&l1, &ll1);
    return 0;
}